package com.nlp.trie.viterbi;

import java.text.DecimalFormat;

public class HMMDecoder {
	StateList states;
	int state_start;
	int state_end;
	
	public IntegerList sequence;//记录解码结果
	public double[][] matrix_maxprob;//记录累积最大概率
	public int[][] matrix_prevstate;//记录最佳前驱状态
	public SymbolList symbols;
	public int stage,i0,i1;
	public boolean laststage;
	public String status, status2;
	
	public HMMDecoder() {
		status = "Not initializd";
		status2 = "";
		states = new StateList();
	}
	
	public void addStartState(State st) {
		state_start = states.size();//get current index
		states.add(st);
	}
	public void addNormalState(State st) {
		states.add(st);
	}
	public void addEndState(State st) {
		state_end = states.size();//get current index
		states.add(st);
		
	}
	
	/**
	 * 调试 degugging 206页
	 */
	public void showmatrix() {
		for (int i = 0; i < symbols.size(); i++) {
			for (int j = 0; j < states.size(); j++) {
				System.out.print(matrix_maxprob[i][j]+" "
						+matrix_prevstate[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public void initialize(SymbolList syms) {
		symbols = syms;
		matrix_maxprob = new double[symbols.size()][states.size()];
		matrix_prevstate = new int[symbols.size()][states.size()];
		for (int i = 0; i < symbols.size(); i++) {
			for (int j = 0; j < states.size(); j++) {
				matrix_prevstate[i][j] = -1;
			}
		}
		Symbol start = symbols.get(0);
		for (int i = 0; i < states.size(); i++) {
			matrix_maxprob[0][i] = states.get(i).emitprob(start);
			matrix_prevstate[0][i] = 0;
		}
		
		stage = 0;
		i0 = -1;
		i1 = -1;
		sequence = new IntegerList();
		status = "Ok, let's get started...";
		status2 = "";
	}
	
	/**
	 * 前向积累过程
	 * @return
	 */
	public boolean proceed_decoding() {
		status2 = "";
		//already end ?
		if (symbols.size() < stage) {
			return false;
			
		}
		
		//not started?
		if (stage == 0) {
			stage = 1;
			i0 = 0;
			i1 = 0;
			matrix_maxprob[stage][i1] = 0.0;
		}else {
			 i0++;
			 if (states.size() <= i0) {
				//i0 should be reinitialized.
				 i0 = 0;
				 i1++;
				 if (states.size() <= i1) {
					 //i1 should be reinitialized
					 // goto next stage.
					stage++;
					if (symbols.size() <= stage) {
						//done.
						status = "Decoding finished.";
						return false;
					}
					laststage = (stage == symbols.size()-1);
					i1 = 0;
				}
				 matrix_maxprob[stage][i1] = 0.0;
			}
		}
		// sym1:next symbol
		Symbol sym1 = symbols.get(stage);
		State s0 = states.get(i0);
		State s1 = states.get(i1);
		
		//precond:1 <= stage.
		double prob = matrix_maxprob[stage-1][i0];
		DecimalFormat form = new DecimalFormat("0.0000");
		status = "Prob:"+form.format(prob);
		
		//skip first stage.
		double transprob = s0.transprob(s1);
		prob = prob*transprob;
		status = status+" x "+form.format(transprob);
		
		double emitprob = s1.emitprob(sym1);
		//这一步的累积概率是上一步的累积概率 * 上一个状态到这个状态的转移概率 * 当前节点的发射概率
		prob = prob * emitprob;
		
		status = status + " x "+form.format(emitprob)+"("+s1.name+":"+sym1.name+")";
		status = status+ " = "+ form.format(prob);
		
		//找到当前节点的最大累积概率
		if (matrix_maxprob[stage][i1] < prob) {
			//记录当前节点的最大累积概率
			matrix_maxprob[stage][i1] = prob;
			//记录当前节点的最佳前驱
			matrix_prevstate[stage][i1] = i0;
			status2 = "(new maximum found)";
		}
		
		return true;
	}
	/**
	 * 反向回溯寻找最佳路径过程
	 */
	public void backward() {
		int probmaxstate = state_end;//结束阶段对应的最大隐状态编号
		sequence.add(probmaxstate);
		//从后往前找最大的隐状态
		for (int i = symbols.size()-1; i > 0; i--) {
			probmaxstate = matrix_prevstate[i][probmaxstate];
			if (probmaxstate == -1) {
				status2 = "Decoding failed.";
				return;
			}
			sequence.add(probmaxstate);//被选中的隐状态加入到结果路径
		}
	}

}
